//
// Created by Snow on 2023/3/12.
//
#include<cstdio>
#include<cstdlib>
#define MaxSize 40
#define M 8
#define N 8
int mg[M+2][N+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},
                  {1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},
                  {1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},
                  {1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},
                  {1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};
typedef struct
{
    int i;//当前方块的行号
    int j;//当前方块的列号
    int di;//di是走到下一相邻可走方块的方位号
}Box;
typedef struct
{
    Box data[MaxSize];
    int top;
}StType;
void InitStack(StType *&s)
{
    s=(StType *)malloc(sizeof(StType));
    s->top=-1;
}
void DestroyStack(StType *&s)
{
    free(s);
}
bool StackEmpty(StType *s)
{
    return (s->top==-1);
}
bool Push(StType *&s,Box e)
{
    if(s->top==MaxSize-1)
        return false;
    s->top++;
    s->data[s->top]=e;
    return true;
}
bool Pop(StType *&s,Box &e)
{
    if(s->top==-1)
        return false;
    e=s->data[s->top];
    s->top--;
    return true;
}
bool GetTop(StType *s,Box &e)
{
    if(s->top==-1)
        return false;
    e=s->data[s->top];
    return true;
}
bool mgpath(int xi,int yi,int xe,int ye)//求解路径为（xi，yi）->（xe,ye)
{
    Box path[MaxSize],e;
    int i,j,di,i1,j1,k;
    bool find;
    StType *st;
    InitStack(st);
    e.i=xi;//设e为入口
    e.j=yi;
    e.di=-1;
    Push(st,e);//方块e进栈
    mg[xi][yi]=-1;//将入口的迷宫值置为-1，避免重复走到改方块
    while(!StackEmpty(st))
    {
        GetTop(st,e);
        i=e.i;
        j=e.j;
        di=e.di;
        if(i==xe&&j==ye)//找到了出口，输出该路径
        {
            printf("the way is:\n");
            k=0;//k表示路径中的方块数
            while(!StackEmpty(st))
            {
                Pop(st,e);
                path[k++]=e;//将e添加到path数组中
            }
            while(k>0)
            {
                printf("\t(%d,%d)",path[k-1].i,path[k-1].j);
                if((k+1)%5==0)
                    printf("\n");
                k--;
            }
            printf("\n");
            DestroyStack(st);
            return true;
        }
        find=false;
        while(di<4&&!find)//找到方块(i,j)的下一个相邻可走方块(i1,j1)
        {
            di++;
            switch(di)
            {
                case 0:i1=i-1;j1=j;break;
                case 1:i1=i;j1=j+1;break;
                case 2:i1=i+1;j1=j;break;
                case 3:i1=i;j1=j-1;break;
            }
            if(mg[i1][j1]==0)find=true;//找到了一个相邻可走方块(i1,j1)
        }
        if(find)
        {
            st->data[st->top].di=di;
            e.i=i1;
            e.j=j1;
            e.di=-1;
            Push(st,e);
            mg[i1][j1]=-1;//将迷宫值置为-1，避免重负走到该方块
        }
        else
        {
            Pop(st,e);//没有路径可走，则退栈
            mg[e.i][e.j]=0;//让退栈方块的位置变成其他路径可走的方块
        }
    }
    DestroyStack(st);
    return false;
}
int main()
{
    if(!mgpath(1,1,M,N))
        printf("fail\n");
    return 1;
}